//
// Description: 5959. 使数组 K 递增的最少操作次数
// Created by Loading on 2021/12/19.
//

#include <bits/stdc++.h>

using namespace std;

int kIncreasing(vector<int> &arr, int k) {
    /* 题意解释为：k 个序列，均变成单调不减序列的最少操作次数 */
    int n = arr.size();
    int res = 0;
    for (int i = 0; i < k; ++i) {
        vector<int> v;
        int len = 0;
        /* 序列长度 - 最长单调不减子序列长度 即为最少操作次数 */
        for (int j = i; j < n; j += k) {
            ++len;
            auto it = upper_bound(v.begin(), v.end(), arr[j]);
            if (it != v.end()) {
                *it = arr[j];
            } else {
                v.emplace_back(arr[j]);
            }
        }
        res += len - (int) v.size();
    }

    return res;
}

int main() {
    vector<int> arr = {4, 1, 5, 2, 6, 2};
    int k = 3;
    int res = kIncreasing(arr, k);
    cout << res << endl;

    return 0;
}
